#include <stdio.h>
#include <stdlib.h>

#define ArrLen 1000  // 定义数组最大长度

void merge(int arr[], int start, int mid, int end) {
    int result[ArrLen];  // 放最终结果的数组
    int k = 0;
    int i = start;  // 归并1段开始位置
    int j = mid + 1;  // 归并2段开始位置
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j]) {  // 段1小就将段1首元素进入结果数组result
            result[k++] = arr[i++];
        }
        else {  // 否则就是段2小,就将段2首元素进入结果数组result
            result[k++] = arr[j++];
        }
    }
    if (i == mid + 1) {  // 如果段1已经全并完成,则循环将段2剩余元素直接并入结果
        while (j <= end)
            result[k++] = arr[j++];
    }
    if (j == end + 1) {  // 如果段2已经全并完成,则循环将段1剩余元素直接并入结果
        while (i <= mid)
            result[k++] = arr[i++];
    }
    for (i = 0, j = start; i < k; i++, j++) {  // 将合并结果再次拷贝到原数组
        arr[j] = result[i];
    }
}

// mergeSort函数
void mergeSort(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = (start + end) / 2;
    mergeSort(arr, start, mid);  // 递归不断分解左半部分
    mergeSort(arr, mid + 1, end);  // 递归不断分解右半部分
    merge(arr, start, mid, end);  // 在递归一个元素时开始归并执行合并操作
}

// 打印数组
void PrintArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 检查数组是否已排序
int IsSorted(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i-1]) {
            return 0;  // 未排序
        }
    }
    return 1;  // 已排序
}

// 复制数组
void CopyArray(int src[], int dest[], int n) {
    for (int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

// 测试归并排序函数
void TestMergeSort(int original[], int n, const char* testName) {
    printf("=== %s ===\n", testName);
    printf("原始数组: ");
    PrintArray(original, n);
    
    int arr[n];
    CopyArray(original, arr, n);
    
    mergeSort(arr, 0, n - 1);
    printf("排序后结果: ");
    PrintArray(arr, n);
    printf("排序正确性: %s\n", IsSorted(arr, n) ? "✓ 正确" : "✗ 错误");
    printf("\n");
}

// 主测试函数
void TestMergeSortComprehensive() {
    printf("========== mergeSort 函数测试 ==========\n\n");
    
    // 测试用例1：一般情况
    int test1[] = {64, 34, 25, 12, 22, 11, 90};
    int n1 = sizeof(test1) / sizeof(test1[0]);
    TestMergeSort(test1, n1, "测试1：一般情况");
    
    // 测试用例2：已排序数组
    int test2[] = {1, 2, 3, 4, 5};
    int n2 = sizeof(test2) / sizeof(test2[0]);
    TestMergeSort(test2, n2, "测试2：已排序数组");
    
    // 测试用例3：逆序数组
    int test3[] = {5, 4, 3, 2, 1};
    int n3 = sizeof(test3) / sizeof(test3[0]);
    TestMergeSort(test3, n3, "测试3：逆序数组");
    
    // 测试用例4：重复元素
    int test4[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    int n4 = sizeof(test4) / sizeof(test4[0]);
    TestMergeSort(test4, n4, "测试4：重复元素");
    
    // 测试用例5：单个元素
    int test5[] = {42};
    int n5 = sizeof(test5) / sizeof(test5[0]);
    TestMergeSort(test5, n5, "测试5：单个元素");
    
    // 测试用例6：两个元素
    int test6[] = {2, 1};
    int n6 = sizeof(test6) / sizeof(test6[0]);
    TestMergeSort(test6, n6, "测试6：两个元素");
}

// 主函数
int main() {
    TestMergeSortComprehensive();
    return 0;
}